package algorithm;

public class leetcode_0873 {
    public int lenLongestFibSubseq(int[] A) {
           //记录最大的斐波那契数列的长度
           int maxLength = 0;
           int length = A.length;
           int[][] dp = new int[length][length];
           for (int j = 2; j < length; j++) {//确定A[j]
               //左右两个指针
               int left = 0;
               int right = j - 1;
                while (left < right) {
                        //两个指针指向值的和
                        int sum = A[left] + A[right];
                        if (sum > A[j]) {
                              //因为数组是递增的，如果两个指针指向的值
                              //大了，那么右指针往左移一步来减小他俩的和
                              right--;
                          } else if (sum < A[j]) {
                              //如果两个指针指向的值小了，那么左指针往
                              //右移一步来增大他俩的和
                              left++;
                          } else {
                              //如果两个指针指向的和等于A[j]，说明这两个指针
                              //指向的值和A[j]可以构成斐波那契数列
                              dp[right][j] = dp[left][right] + 1;
                              maxLength = Math.max(maxLength, dp[right][j]);
                              right--;
                              left++;
                          }
                  }
              }
            return maxLength > 0 ? maxLength + 2 : 0;
        }
}
